'''
        不懂！！！！！！！！！！！！

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:
 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]
示例2:
 输入：S = "ab"
 输出：["ab", "ba"]
-----------------------------------------------------
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutation-ii-lcci
'''

from typing import List

# 实在太难了，记住回溯算法的格式就好了
# 一般两个中介，一个记录输入成员的下标，一个记录结果
# 存在重复元素的时候，要进行排列，那么第一次出现的重复元素一定要被取了，才能取后面的重复元素，也就是，第一个都不取，后面的重复元素都不能考虑取
'''格式
def back(内容):
    if 满足条件：
        append(i)
        return
    for循环：
        # 主要是排除不符合的条件，然后继续推进前向运算的，比如把坐标指向下一个
        if 不满足条件：
            continue/return
        back(内容) #继续嵌套回溯增加成员
        .pop / =0 # 删除元素，退出返回上一个嵌套回溯
'''
class Solution:
    def permutation(self, S_in: str) -> List[str]:
        S_in = sorted(S_in)
        res = []
        seen = [0] * len(S_in) # 1表示对应下标的字符被取了， 0表示还没取的字符或者当前为头的字符

        # 回溯法
        def back(s):
            # print('包含最内层的s：', s) #内层
            if len(s) == len(S_in):
                # print('res',res)
                res.append(s)
                # print('return')
                # 排列出来一个符合的字符串就返回，
                # 不是重复字符就回到回溯前最外层处，
                # 遇到重复字符，就回退到次外层
                return
            for j in range(len(S_in)):
                if seen[j]: # 在不断嵌套回溯的过程中，外面访问过得成员就会是1，即不会被重复访问
                    # 被访问过了就跳过
                    continue
                if j > 0 and S_in[j] == S_in[j-1] and not seen[j-1]:
                    # j > 0：已经取了一个以上的字符了
                    # S_in[j] == S_in[j-1] 如果存在重复字符
                    # not seen[j-1] 存在重复字符只取第一次出现的，如果第一个重复的字符没被取，那么这个重复字符可能已经被取过了
                    continue
                # print('seen2: ', seen)
                seen[j] = 1 # 现在访问此字符，置1表示已访问，然后进入内部循环back()，准备访问下一个字符
                # print('除去最内层的s:',s) # 外层
                '''每个嵌套的back()里面的s是不一样的'''
                back(s+S_in[j]) # 循环调用 # 上面的return就是回到这里 # continue 退出的循环也是回到这
                seen[j] = 0

        back("")
        return res



S = "qqqe"
solu = Solution()
print(solu.permutation(S))








